Search Results

Documents authored by Li, Jason

Document
DOI: 10.4230/DagRep.13.10.76
Graph Algorithms: Cuts, Flows, and Network Design (Dagstuhl Seminar 23422)

Authors: Jason Li, Debmalya Panigrahi, Laura Sanita, and Thatchaphol Saranurak

Published in: Dagstuhl Reports, Volume 13, Issue 10 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23422 "Graph Algorithms: Cuts, Flows, and Network Design". This seminar brought 25 leading researchers in graph algorithms together for a discussion of the recent progress and challenges in two areas: the design of fast algorithm for fundamental flow/cut problems and the design of approximation algorithms for basic network design problems. The seminar included several talks of varying lengths, a panel discussion, and an open problem session. In addition, sufficient time was set aside for research discussions and collaborations.
Cite as

Jason Li, Debmalya Panigrahi, Laura Sanita, and Thatchaphol Saranurak. Graph Algorithms: Cuts, Flows, and Network Design (Dagstuhl Seminar 23422). In Dagstuhl Reports, Volume 13, Issue 10, pp. 76-89, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{li_et_al:DagRep.13.10.76,
  author =	{Li, Jason and Panigrahi, Debmalya and Sanita, Laura and Saranurak, Thatchaphol},
  title =	{{Graph Algorithms: Cuts, Flows, and Network Design (Dagstuhl Seminar 23422)}},
  pages =	{76--89},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{10},
  editor =	{Li, Jason and Panigrahi, Debmalya and Sanita, Laura and Saranurak, Thatchaphol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.10.76},
  URN =		{urn:nbn:de:0030-drops-198357},
  doi =		{10.4230/DagRep.13.10.76},
  annote =	{Keywords: approximation, graph algorithm, maximum flow, minimum cut, network design}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.66
O(1) Steiner Point Removal in Series-Parallel Graphs

Authors: D. Ellis Hershkowitz and Jason Li

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We study how to vertex-sparsify a graph while preserving both the graph’s metric and structure. Specifically, we study the Steiner point removal (SPR) problem where we are given a weighted graph G = (V,E,w) and terminal set V' ⊆ V and must compute a weighted minor G' = (V',E', w') of G which approximates G’s metric on V'. A major open question in the area of metric embeddings is the existence of O(1) multiplicative distortion SPR solutions for every (non-trivial) minor-closed family of graphs. To this end prior work has studied SPR on trees, cactus and outerplanar graphs and showed that in these graphs such a minor exists with O(1) distortion. We give O(1) distortion SPR solutions for series-parallel graphs, extending the frontier of this line of work. The main engine of our approach is a new metric decomposition for series-parallel graphs which we call a hammock decomposition. Roughly, a hammock decomposition is a forest-like structure that preserves certain critical parts of the metric induced by a series-parallel graph.
Cite as

D. Ellis Hershkowitz and Jason Li. O(1) Steiner Point Removal in Series-Parallel Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 66:1-66:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hershkowitz_et_al:LIPIcs.ESA.2022.66,
  author =	{Hershkowitz, D. Ellis and Li, Jason},
  title =	{{O(1) Steiner Point Removal in Series-Parallel Graphs}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{66:1--66:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.66},
  URN =		{urn:nbn:de:0030-drops-170041},
  doi =		{10.4230/LIPIcs.ESA.2022.66},
  annote =	{Keywords: Metric embeddings, graph algorithms, vertex sparsification}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.52
Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs

Authors: Zhiyang He, Jason Li, and Magnus Wahlström

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Let G be a graph and S, T ⊆ V(G) be (possibly overlapping) sets of terminals, |S| = |T| = k. We are interested in computing a vertex sparsifier for terminal cuts in G, i.e., a graph H on a smallest possible number of vertices, where S ∪ T ⊆ V(H) and such that for every A ⊆ S and B ⊆ T the size of a minimum (A,B)-vertex cut is the same in G as in H. We assume that our graphs are unweighted and that terminals may be part of the min-cut. In previous work, Kratsch and Wahlström (FOCS 2012/JACM 2020) used connections to matroid theory to show that a vertex sparsifier H with O(k³) vertices can be computed in randomized polynomial time, even for arbitrary digraphs G. However, since then, no improvements on the size O(k³) have been shown. In this paper, we draw inspiration from the renowned Bollobás’s Two-Families Theorem in extremal combinatorics and introduce the use of total orderings into Kratsch and Wahlström’s methods. This new perspective allows us to construct a sparsifier H of Θ(k²) vertices for the case that G is a DAG. We also show how to compute H in time near-linear in the size of G, improving on the previous O(n^{ω+1}). Furthermore, H recovers the closest min-cut in G for every partition (A,B), which was not previously known. Finally, we show that a sparsifier of size Ω(k²) is required, both for DAGs and for undirected edge cuts.
Cite as

Zhiyang He, Jason Li, and Magnus Wahlström. Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.ESA.2021.52,
  author =	{He, Zhiyang and Li, Jason and Wahlstr\"{o}m, Magnus},
  title =	{{Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.52},
  URN =		{urn:nbn:de:0030-drops-146331},
  doi =		{10.4230/LIPIcs.ESA.2021.52},
  annote =	{Keywords: graph theory, vertex sparsifier, representative family, matroid}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.41
On the Fixed-Parameter Tractability of Capacitated Clustering

Authors: Vincent Cohen-Addad and Jason Li

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We study the complexity of the classic capacitated k-median and k-means problems parameterized by the number of centers, k. These problems are notoriously difficult since the best known approximation bound for high dimensional Euclidean space and general metric space is Theta(log k) and it remains a major open problem whether a constant factor exists. We show that there exists a (3+epsilon)-approximation algorithm for the capacitated k-median and a (9+epsilon)-approximation algorithm for the capacitated k-means problem in general metric spaces whose running times are f(epsilon,k) n^{O(1)}. For Euclidean inputs of arbitrary dimension, we give a (1+epsilon)-approximation algorithm for both problems with a similar running time. This is a significant improvement over the (7+epsilon)-approximation of Adamczyk et al. for k-median in general metric spaces and the (69+epsilon)-approximation of Xu et al. for Euclidean k-means.
Cite as

Vincent Cohen-Addad and Jason Li. On the Fixed-Parameter Tractability of Capacitated Clustering. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cohenaddad_et_al:LIPIcs.ICALP.2019.41,
  author =	{Cohen-Addad, Vincent and Li, Jason},
  title =	{{On the Fixed-Parameter Tractability of Capacitated Clustering}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.41},
  URN =		{urn:nbn:de:0030-drops-106171},
  doi =		{10.4230/LIPIcs.ICALP.2019.41},
  annote =	{Keywords: approximation algorithms, fixed-parameter tractability, capacitated, k-median, k-means, clustering, core-sets, Euclidean}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.42
Tight FPT Approximations for k-Median and k-Means

Authors: Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We investigate the fine-grained complexity of approximating the classical k-Median/k-Means clustering problems in general metric spaces. We show how to improve the approximation factors to (1+2/e+epsilon) and (1+8/e+epsilon) respectively, using algorithms that run in fixed-parameter time. Moreover, we show that we cannot do better in FPT time, modulo recent complexity-theoretic conjectures.
Cite as

Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT Approximations for k-Median and k-Means. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cohenaddad_et_al:LIPIcs.ICALP.2019.42,
  author =	{Cohen-Addad, Vincent and Gupta, Anupam and Kumar, Amit and Lee, Euiwoong and Li, Jason},
  title =	{{Tight FPT Approximations for k-Median and k-Means}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.42},
  URN =		{urn:nbn:de:0030-drops-106182},
  doi =		{10.4230/LIPIcs.ICALP.2019.42},
  annote =	{Keywords: approximation algorithms, fixed-parameter tractability, k-median, k-means, clustering, core-sets}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.31
New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms

Authors: Mohsen Ghaffari and Jason Li

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
We show that many classical optimization problems - such as (1 +/- epsilon)-approximate maximum flow, shortest path, and transshipment - can be computed in tau_{mix}(G)* n^o(1) rounds of distributed message passing, where tau_{mix}(G) is the mixing time of the network graph G. This extends the result of Ghaffari et al. [PODC'17], whose main result is a distributed MST algorithm in tau_{mix}(G)* 2^O(sqrt{log n log log n}) rounds in the CONGEST model, to a much wider class of optimization problems. For many practical networks of interest, e.g., peer-to-peer or overlay network structures, the mixing time tau_{mix}(G) is small, e.g., polylogarithmic. On these networks, our algorithms bypass the Omega(sqrt n+D) lower bound of Das Sarma et al. [STOC'11], which applies for worst-case graphs and applies to all of the above optimization problems. For all of the problems except MST, this is the first distributed algorithm which takes o(sqrt n) rounds on a (nontrivial) restricted class of network graphs. Towards deriving these improved distributed algorithms, our main contribution is a general transformation that simulates any work-efficient PRAM algorithm running in T parallel rounds via a distributed algorithm running in T * tau_{mix}(G)* 2^O(sqrt{log n}) rounds. Work- and time-efficient parallel algorithms for all of the aforementioned problems follow by combining the work of Sherman [FOCS'13, SODA'17] and Peng and Spielman [STOC'14]. Thus, simulating these parallel algorithms using our transformation framework produces the desired distributed algorithms. The core technical component of our transformation is the algorithmic problem of solving multi-commodity routing - that is, roughly, routing n packets each from a given source to a given destination - in random graphs. For this problem, we obtain a new algorithm running in 2^O(sqrt{log n}) rounds, improving on the 2^O(sqrt{log n log log n}) round algorithm of Ghaffari, Kuhn, and Su [PODC'17]. As a consequence, for the MST problem in particular, we obtain an improved distributed algorithm running in tau_{mix}(G)* 2^O(sqrt{log n}) rounds.
Cite as

Mohsen Ghaffari and Jason Li. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ghaffari_et_al:LIPIcs.DISC.2018.31,
  author =	{Ghaffari, Mohsen and Li, Jason},
  title =	{{New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.31},
  URN =		{urn:nbn:de:0030-drops-98207},
  doi =		{10.4230/LIPIcs.DISC.2018.31},
  annote =	{Keywords: Distributed Graph Algorithms, Mixing Time, Random Graphs, Multi-Commodity Routing}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.33
Faster Distributed Shortest Path Approximations via Shortcuts

Authors: Bernhard Haeupler and Jason Li

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
A long series of recent results and breakthroughs have led to faster and better distributed approximation algorithms for single source shortest paths (SSSP) and related problems in the CONGEST model. The runtime of all these algorithms, however, is Omega~(sqrt{n}), regardless of the network topology, even on nice networks with a (poly)logarithmic network diameter D. While this is known to be necessary for some pathological networks, most topologies of interest are arguably not of this type. We give the first distributed approximation algorithms for shortest paths problems that adjust to the topology they are run on, thus achieving significantly faster running times on many topologies of interest. The running time of our algorithms depends on and is close to Q, where Q is the quality of the best shortcut that exists for the given topology. While Q = Theta~(sqrt{n} + D) for pathological worst-case topologies, many topologies of interest have Q = Theta~(D), which results in near instance optimal running times for our algorithm, given the trivial Omega(D) lower bound. The problems we consider are as follows: - an approximate shortest path tree and SSSP distances, - a polylogarithmic size distance label for every node such that from the labels of any two nodes alone one can determine their distance (approximately), and - an (approximately) optimal flow for the transshipment problem. Our algorithms have a tunable tradeoff between running time and approximation ratio. Our fastest algorithms have an arbitrarily good polynomial approximation guarantee and an essentially optimal O~(Q) running time. On the other end of the spectrum, we achieve polylogarithmic approximations in O~(Q * n^epsilon) rounds for any epsilon > 0. It seems likely that eventually, our non-trivial approximation algorithms for the SSSP tree and transshipment problem can be bootstrapped to give fast Q * 2^O(sqrt{log n log log n}) round (1+epsilon)-approximation algorithms using a recent result by Becker et al.
Cite as

Bernhard Haeupler and Jason Li. Faster Distributed Shortest Path Approximations via Shortcuts. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{haeupler_et_al:LIPIcs.DISC.2018.33,
  author =	{Haeupler, Bernhard and Li, Jason},
  title =	{{Faster Distributed Shortest Path Approximations via Shortcuts}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.33},
  URN =		{urn:nbn:de:0030-drops-98229},
  doi =		{10.4230/LIPIcs.DISC.2018.33},
  annote =	{Keywords: Distributed Graph Algorithms, Shortest Path, Shortcuts}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.70
Non-Preemptive Flow-Time Minimization via Rejections

Authors: Anupam Gupta, Amit Kumar, and Jason Li

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider the online problem of minimizing weighted flow-time on unrelated machines. Although much is known about this problem in the resource-augmentation setting, these results assume that jobs can be preempted. We give the first constant-competitive algorithm for the non-preemptive setting in the rejection model. In this rejection model, we are allowed to reject an epsilon-fraction of the total weight of jobs, and compare the resulting flow-time to that of the offline optimum which is required to schedule all jobs. This is arguably the weakest assumption in which such a result is known for weighted flow-time on unrelated machines. While our algorithms are simple, we need a delicate argument to bound the flow-time. Indeed, we use the dual-fitting framework, with considerable more machinery to certify that the cost of our algorithm is within a constant of the optimum while only a small fraction of the jobs are rejected.
Cite as

Anupam Gupta, Amit Kumar, and Jason Li. Non-Preemptive Flow-Time Minimization via Rejections. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ICALP.2018.70,
  author =	{Gupta, Anupam and Kumar, Amit and Li, Jason},
  title =	{{Non-Preemptive Flow-Time Minimization via Rejections}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{70:1--70:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.70},
  URN =		{urn:nbn:de:0030-drops-90740},
  doi =		{10.4230/LIPIcs.ICALP.2018.70},
  annote =	{Keywords: Scheduling, Rejection, Unrelated Machines, Non-Preemptive}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact